def kmp(s):
n = len(s)
prefix = [0 for _ in range(n)]
for i in range(1, n):
j = prefix[i - 1]
while j > 0 and s[i] != s[j]:
j = prefix[j - 1]
if s[i] == s[j]:
j += 1
prefix[i] = j
return prefix
if __name__ == '__main__':
s = input()
prefix = kmp(s)
answer = prefix[-1]
if answer == 0:
print("Just a legend")
elif prefix.count(answer) >= 2:
print(s[0:answer])
else:
answer = prefix[answer - 1]
if answer == 0:
print("Just a legend")
else:
print(s[0:answer])
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
int main(){
string s;
cin>>s;
ll n =s.length();
ll kmp[n]={};
ll pointer=0;
kmp[0]=0;
ll cnt[n+3]={};
//cout<<n<<endl;
for (int i =1;i<n;i++){
pointer= kmp[i-1];
while (pointer!=0&&s[i]!=s[pointer]){
pointer=kmp[pointer-1];
//cout<<pointer<<endl;
}
kmp[i]=pointer + (s[i]==s[pointer]);
}
bool check[n]={};
pointer=n;
vector<int> ans;
while (pointer>0){
ans.push_back(pointer);
pointer=kmp[pointer-1];
}
/*for (int i =0 ;i<n;i++){
cout<<kmp[i]<<" ";
}
cout<<endl;*/
for (int i =0;i<n+1;i++){
cnt[i]++;
}
for (int i =n;i>0;i--){
cnt[kmp[i-1]]+=cnt[i];
}
//cout<<ans.size()<<"\n";
int mx=INT_MIN;
for (int i =0;i<ans.size();i++){
if (cnt[ans[i]]>=3){
mx=max(mx,ans[i]);
}
}
if (mx==INT_MIN){
cout<<"Just a legend";
}else cout<<s.substr(0,mx);
}
954A - Diagonal Walking | 39F - Pacifist frogs |
1451C - String Equality | 386A - Second-Price Auction |
1690E - Price Maximization | 282B - Painting Eggs |
440A - Forgotten Episode | 233B - Non-square Equation |
628B - New Skateboard | 262B - Roma and Changing Signs |
755C - PolandBall and Forest | 456B - Fedya and Maths |
376B - IOU | 1623B - Game on Ranges |
1118A - Water Buying | 1462C - Unique Number |
301A - Yaroslav and Sequence | 38A - Army |
38C - Blinds | 1197A - DIY Wooden Ladder |
1717D - Madoka and The Corruption Scheme | 1296D - Fight with Monsters |
729D - Sea Battle | 788A - Functions again |
1245B - Restricted RPS | 1490D - Permutation Transformation |
1087B - Div Times Mod | 1213B - Bad Prices |
1726B - Mainak and Interesting Sequence | 1726D - Edge Split |